package com.ting.test.algorithms.strings;

/**
 * Created by 雷霆 on 2020/3/14.
 * <p>
 * Description：
 * 请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
 * <p>
 *  
 * <p>
 * 示例 1:
 * <p>
 * 输入: "abcabcbb"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
 * 示例 2:
 * <p>
 * 输入: "bbbbb"
 * 输出: 1
 * 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
 * 示例 3:
 * <p>
 * 输入: "pwwkew"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
 *      请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
 *  
 * <p>
 * 提示：
 * <p>
 * s.length <= 40000
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LongestSubStringWIthOutRepeating {
    public static int lengthOfLongestSubstring(String s) {
        if (null == s) {
            return 0;
        }

        char[] chars = s.toCharArray();
        int head = 0;
        int tail = 0;
        int tempLength;
        int length = s.length();
        int subLength = 1;

        while (head <= tail && tail < length) {
            if (tail == head) {
                tail++;
                continue;
            }

            if (check(chars, head, tail) >= 0) {
                head++;
            } else {
                tail++;
                tempLength = tail - head;
                if (tempLength > subLength) {
                    subLength = tempLength;
                }
            }


        }
        return subLength;

    }

    public static int check(char[] chars, int head, int tail) {
        for (int i = head; i < tail; i++) {
            if (chars[i] == chars[tail]) {
                return i;
            }
        }
        return -1;
    }


    public static void main(String[] args) {
        String str = "abca";
        int leng = lengthOfLongestSubstring(str);
        System.out.println(leng);
    }
}
